654. 最大二叉树

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归

var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) {
        return null;
    }

    // 找到 nums 中最大的数的 index
    // 然后划分出前缀数组和后缀数组
    // 为了避免反复比较大小, 再第一次遍历时就维护好一个数据结构方便查询最大的?
    // 还没学会这么屌的结构, 其实是最大堆? 那还是乖乖遍历好了
    let max = 0;
    let maxIndex = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > max) {
            max = nums[i];
            maxIndex = i;
        }
    }

    const node = new TreeNode(max);
    node.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    node.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return node;
};